package leetcode;

/**
 * P10. 正则表达式匹配
 */
public class RegexMatcher {

    public static void main(String[] args) {
        String word = "";
        String pattern = ".";
//        String sub = word.substring(1, word.length());
//        System.out.println("sub is: [" + sub + "]");
        RegexMatcher object = new RegexMatcher();
        System.out.println(object.isMatch(word, pattern));
    }

    /**
     * 判断word是否匹配pattern
     * pattern只包括正则中的. 和 *。 .表示匹配任意字符；*表示它前面的字符可以出现任意次，包括0次
     */
    public boolean isMatchWrong(String word, String pattern) {
        if (word == null || pattern == null) {
            return false;
        }
        int length = word.length();
        int patternLength = pattern.length();
        int index = 0;
        for (int i = 0; i < patternLength;) {
            // 这个逻辑有问题，比如"ab" 和".*c" 显然就不匹配
//            if (pattern.charAt(i) == '.' && i < patternLength - 1
//                    && pattern.charAt(i + 1) == '*') {
//                // 遇到.* 肯定之后的都可以匹配了，直接返回
//                return true;
//            }
            if (pattern.charAt(i) == '.' && i < patternLength - 1
                    && pattern.charAt(i + 1) == '*') {
                // 遇到这种情况，就是要么匹配当前字符串，要么不匹配当前字符串(*取0)
                // 不匹配当前字符串
                boolean res = isMatch(word.substring(index, length), pattern.substring(i + 2, patternLength));;
                if (index != length) {
                    // 匹配当前字符串
                    res |= isMatch(word.substring(index + 1, length), pattern.substring(i, patternLength));
                }
                return res;
            } else if (i < patternLength - 1 && pattern.charAt(i + 1) == '*') {
                // 这个逻辑也有问题
                // 比如"aaa" 和"a*a"
                // 这个是贪心的，会匹配三个a
                // 如果后面的是通配符*，匹配所有与当前相等的字符
                while (index < length && word.charAt(index) == pattern.charAt(i)) {
                    index++;
                }
                i += 2;
            } else if (pattern.charAt(i) == '.' ||
                    (index < length && pattern.charAt(i) == word.charAt(index))) {
                index++;
                i++;
            } else {
                return false;
            }
        }
        return index == length;
    }

    /**
     * 判断word是否匹配pattern
     * pattern只包括正则中的. 和 *。 .表示匹配任意字符；*表示它前面的字符可以出现任意次，包括0次
     *
     * 递归的方式，但是这种方式很慢
     * 执行用时：633 ms, 在所有 Java 提交中击败了5.10%的用户
     * 内存消耗：39.1 MB, 在所有 Java 提交中击败了5.04%的用户
     */
    public boolean isMatch(String word, String pattern) {
        System.out.println("word: " + word + "  pattern: " + pattern);
        if (word == null || pattern == null) {
            return false;
        }
        int length = word.length();
        int patternLength = pattern.length();
        int index = 0;
        for (int i = 0; i < patternLength;) {
            // 这个逻辑有问题，比如"ab" 和".*c" 显然就不匹配
//            if (pattern.charAt(i) == '.' && i < patternLength - 1
//                    && pattern.charAt(i + 1) == '*') {
//                // 遇到.* 肯定之后的都可以匹配了，直接返回
//                return true;
//            }
            if (i < patternLength - 1
                    && pattern.charAt(i + 1) == '*') {
                // 如果后面是'*'，就是要么匹配当前字符串，要么不匹配当前字符串(*取0)

                // 不匹配当前字符串
                System.out.println("index:" + index + " length: " + length);
                boolean res = isMatch(word.substring(index, length), pattern.substring(i + 2, patternLength));;

                if (index != length && (pattern.charAt(i) == '.' || word.charAt(index) == pattern.charAt(i))) {
                    // 匹配当前字符串
                    res |= isMatch(word.substring(index + 1, length), pattern.substring(i, patternLength));
                }
                return res;
            } else if (index < length
                    && (pattern.charAt(i) == '.' || pattern.charAt(i) == word.charAt(index))) {
                // 这个应该是index < length 并且字符匹配
                // 比如"a" 和 ".." 是不匹配的
                index++;
                i++;
            } else {
                return false;
            }
        }
        return index == length;
    }

    public boolean isMatchFaster(String word, String pattern) {
        System.out.println("word: " + word + "  pattern: " + pattern);
        if (word == null || pattern == null) {
            return false;
        }
        int length = word.length();
        int patternLength = pattern.length();
        int index = 0;
        // 采用动态规划的思路来做

        return index == length;
    }
}
